package com.ywk.base.dataStructure.linkedlist;

import java.util.Stack;

public class LinkedListDemo {

	public static void main(String[] args) {
		LinkedNode ld1=new LinkedNode(1, "张三");
		LinkedNode ld2=new LinkedNode(2, "李四");
		LinkedNode ld3=new LinkedNode(3, "赵五");
		LinkedNode ld4=new LinkedNode(4, "小二");
		LinkedNode ld5=new LinkedNode(5, "鷄");
		LinkedNode ld6=new LinkedNode(6, "孑");
		LinkedNode ld7=new LinkedNode(7, "IK");
		LinkedNode ld8=new LinkedNode(8, "SA");
		LinkedNode ld9=new LinkedNode(9, "AF");
		
//		LinkedList1 ll=new LinkedList1();//无序链表
//		ll.addNode(ld2);
//		ll.addNode(ld1);
//		ll.addNode(ld3);
//		ll.showLinked();
		
		LinkedList l2=new LinkedList();//有序链表
		l2.addNode(ld5);
		l2.addNode(ld8);
		l2.addNode(ld1);
		l2.addNode(ld6);
		l2.addNode(ld2);
		
		System.out.println("原始的有序链表各节点：");
		l2.showLinked();
//
//		System.out.println("从尾到头打印链表结点：");
//		l2.showLinkedListByStack();
//		
//		l2.deleteNode(ld2);
//		System.out.println("删除第二个结点后：");
//		l2.showLinked();
//		
//		l2.deleteNode(ld4);
//		
//		LinkedNode nld=new LinkedNode(1, "张三···");
//		l2.updateNode(nld);
//		System.out.println("修改结点后：");
//		l2.showLinked();
//		
//		System.out.println("单链表中倒数第二个结点是：");
//		l2.queryNode(2);
//		
//		l2.reverse();
//		System.out.println("反转后的单链表：");
//		l2.showLinked();
		
		LinkedList l3=new LinkedList();
		l3.addNode(ld7);
		l3.addNode(ld3);
		l3.addNode(ld4);
		l3.addNode(ld9);
		
		System.out.println("l3合并前：");
		l3.showLinked();
		System.out.println("l3合并l2单链表后：");
		l3.mergeLinkedList(l2);
		l3.showLinked();
		
	}

}

//有序链表：新结点按编号大小添加到链表中
class LinkedList {
	//每创建一个链表就附带一个头结点
	private LinkedNode head=new LinkedNode(0, "");
	
	public void addNode(LinkedNode ln) {
		//只有头结点的情况
		if(head.next==null) {
			head.next=ln;
			return;
		}else if(ln.getNo()<head.next.getNo()) {//有两个结点的时候，包括头结吧点
			//下面两句代码顺序不能写反（等号"="左边的是指针，右边的是实例对象）
			ln.next=head.next;
			head.next=ln;
			return;
		}
		LinkedNode p=head.next;
		while(true) {
			if(ln.getNo()==p.getNo()) {
				System.out.println("链表中已存在，添加失败");
			}else if(p.next==null) {//当p指向的是最后一个结点时
				p.next=ln;
				break;
			}else if(ln.getNo()>p.getNo()&&ln.getNo()<p.next.getNo()){
				//下面两句代码顺序不能反（等号"="左边的是指针，右边的是实例对象）
				ln.next=p.next;
				p.next=ln;
				break;
			}
			p=p.next;
		}
	}
	//单链表中设置的遍历指针（即：p）只能往后移动，不能往前移动，所以要删除某个结点时，应将
	//p指针指向该结点的前一个结点，通过前面的结点来删除后面的结点,被删除的节点不会被其他引用指向，就会被垃圾回收机制回收
	public void deleteNode(LinkedNode ln) {
		LinkedNode p=head.next;
		if(p.next==null) {
			System.out.println("链表为空、、、");
			return;
		}
		while(true) {
			if(p.next==null) {
				System.out.println("no="+ln.getNo()+"的节点不存在");
				break;
			}
			if(p.next.getNo()==ln.getNo()) {
				p.next=p.next.next;
				System.out.println("no="+ln.getNo()+"的节点删除成功");
				break;
			} 
			p=p.next;
		}
	}
	
	public void updateNode(LinkedNode ln) {
		LinkedNode p=head.next;
		//boolean flage=false;
		if(p==null) {
			System.out.println("链表为空");
		}
		while(true) {
			if(p.getNo()==ln.getNo()) {
				//flage=true;
				p.setName(ln.getName());
				System.out.printf("%d修改成功\n",ln.getNo());
				break;
			}else if(p.next==null){
				System.out.println("不存在该节点");
				break;
			}
			p=p.next;
		}
//		if(flage) {
//			p.setName(ln.getName());
//			System.out.printf("%d修改成功\n",ln.getNo());
//		}else {
//			System.out.println("不存在该节点");
//      	break;
//		}
	}
	
	//获取单链表结点个数
	public int nodeCount() {
		int count=0;
		LinkedNode p=head;
		while(true) {
			if(p.next==null) {
				break;
			}
			count++;
			p=p.next;
		}
		return count;
	}
	
	//查找单链表中倒数第i个结点
	public void queryNode(int i) {
		//先计算单链表结点总数
		int count=nodeCount();
		LinkedNode ln=new LinkedNode();
		LinkedNode p=head;
		for(int j=0;j<count-i+1;j++) {
			p=p.next;
		}
		ln=p;
		System.out.println(ln);
	}
	
	
	public void showLinked() {
		if(head.next==null) {
			System.out.println("链表为空、、、");
			return;
		}
		LinkedNode p=head.next;
		while(true) {
			System.out.println(p);
			if(p.next==null) {
				break;
			}
			p=p.next;
		}
	}
	
	//单链表的反转
	//经测试，两个辅助指针不能完成反转（原因：当反转第二个结点，辅助指针往后移动之后，
	//没有指针引用最前面的结点，导致后续结点不能反转）,用三个辅助指针能完成反转
	//（也可以创建新的单链表头结点，用插入法将每个节点插入到新的头结点的后面，最后再将原头结点指向新头节点的下一个）
	public void reverse() {
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}else if(head.next.next==null) {
			System.out.println("链表只有一个结点，不用反转");
			return;
		}
		LinkedNode font=head.next;//尾指针(即：指向第一个节点)
		LinkedNode p=head.next.next;//(即：指向第二个节点)
		LinkedNode rear=head.next.next.next;//头指针(即：指向第三个节点)
		font.next=null;
		//只有两个节点的情况
		if(rear==null) {
			p.next=font;
			head.next=p;
			return;
		}
		//三个及三个结点以上
		while(rear!=null){
            p.next=font;
            font=p;
            p=rear;
            rear=rear.next;
        }
        p.next=font;
        head.next=p;
		
//		while(true) {
//			p.next=font;
//			font=rear.next;//(1)每反转一个结点就将最前面的指针移到最后面的指针的下一个节点上（每反转三个节点为一个回合）
//			if(font==null) {//每反转一个结点就进行判断后移的指针指向的结点是否为空
//				rear.next=p;
//				head.next=rear;
//				break;
//			}
//			rear.next=p;
//			p=font.next;//(2)
//			if(p==null) {
//				font.next=rear;
//				head.next=font;
//				break;
//			}
//			font.next=rear;
//			rear=p.next;//(3)
//			if(rear==null) {
//				p.next=font;
//				head.next=p;
//				break;
//			}
//		}
	}
	
	//在不改变单链表结构的前提下从尾到头打印单链表的结点（利用栈的特点来实现）
	public void showLinkedListByStack() {
		Stack<LinkedNode> s=new Stack<LinkedNode>();
		LinkedNode p =head.next;
		while(true) {
			s.add(p);//add和push方法都可以实现，这两个方法的区别在于返回值不一样
			//s.push(p);
			if(p.next==null) {
				break;
			}
			p=p.next;
		}
		while(s.size()>0) {
			System.out.println(s.pop());
		}
	}
	
	//合并两个单链表成一个有序链表
	public void mergeLinkedList(LinkedList l) {
		LinkedNode p2=l.head.next;
		LinkedNode p1;
		LinkedNode temp;//用来保留p2下一个结点（关键/重点）
		if(p2==null) {
			return;
		}
		while(true) {
			p1=this.head.next;//没将一个结点插入到this链表后重置辅助指针到第一个节点
			while(true) {
				if(p1==null) {
					temp=p2.next;//用来保留p2下一个结点（关键）
					this.head.next=p2;
					p2.next=null;
					p2=temp;//让p2后移
					break;
				}else if(p2.getNo()<=p1.getNo()) {//小于第一个节点的情况
					temp=p2.next;
					p2.next=p1;
					this.head.next=p2;
					p2=temp;
					break;
				}else if(p2.getNo()>=p1.getNo()&&p2.getNo()<=p1.next.getNo()) {
					temp=p2.next;
					p2.next=p1.next;
					p1.next=p2;
					p2=temp;
					break;
				}else if(p1.next==null) {
					temp=p2.next;
					p1.next=p2;
					p2.next=null;
					temp=p2.next;
					break;
				}
				p1=p1.next;
			}
			if(p2==null) {
				break;
			}
		}
	}
	
	
}



//无序链表：新结点添加到链表的最后面
class LinkedList1{
	//head为头结点，每创建一个链表的同时就有一个头结点，该节点内没有任何数据的
	private LinkedNode head=new LinkedNode(0,"");//
	
	public void addNode(LinkedNode ln) {
		//p为辅助指针（可以移动），用来遍历链表结点的，先让它指向头结点
		LinkedNode p=head;
		while(true) {
			if(p.next==null) {//找到最后面的结点，将新结点添加到最后
				break;
			}
			p=p.next;//使p指向后继结点（即：指针后移）
		}
		p.next=ln;
	}
	
	public void deleteNode(LinkedNode ln) {
		LinkedNode p=head.next;
		if(p.next==null) {
			System.out.println("链表为空、、、");
			return;
		}
		while(true) {
			if(p.getNo()<ln.getNo()&&p.next.getNo()==ln.getNo()) {
				p.next=p.next.next;
				System.out.println("no="+ln.getNo()+"的节点删除成功");
				break;
			}else if(p.next==null) {
				System.out.println("no="+ln.getNo()+"的节点不存在");
				break;
			}
			p=p.next;
		}
	}
	
	public void showLinked() {
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		LinkedNode p=head.next;//让p指向no=1的结点（即：头结点的下一个结点）
		while(true) {
			System.out.println(p);
			if(p.next==null) {
				break;
			}
			p=p.next;//使p指向后继结点（即：指针后移）
		}
	}
}


class LinkedNode{
	private int no;
	private String name;
	public LinkedNode next;
	
	public LinkedNode() {}
	
	public LinkedNode(int no,String name) {
		this.no=no;
		this.name=name;
	}
	
	public String getName() {
		return name;
	}
	
	public void setName(String name) {
		this.name=name;
	}
	
	public int getNo() {
		return no;
	}
	
	public LinkedNode getNext() {
		return next;
	}
	
	@Override
	public String toString() {
		return "LinkedNode [no=" + no + ",name=" + name + "]";
	}
	
}




